/**
 * 992. K 个不同整数的子数组
 * https://leetcode-cn.com/problems/subarrays-with-k-different-integers/
 */
public class Solutions_992 {
    public static void main(String[] args) {
//        int[] A = {1, 2, 1, 2, 3};
//        int K = 2;  // output: 7
//        解释：恰好由 2 个不同整数组成的子数组：{1, 2},  {2, 1},  {1, 2},  {2, 3},  {1, 2, 1},  {2, 1, 2},  {1, 2, 1, 2}.

//        int[] A = {1, 2, 1, 3, 4};
//        int K = 3;  // output: 3
//        解释：恰好由 3 个不同整数组成的子数组：{1, 2, 1, 3},  {2, 1, 3},  {1, 3, 4}

        int[] A = {2, 1, 1, 1, 2};
        int K = 1;  // output: 8
        // {{2}, {1}, {1}, {1}, {1, 1}, {1, 1}, {1, 1, 1}, {2}}

        int result = subarraysWithKDistinct(A, K);
        System.out.println(result);
    }

    public static int subarraysWithKDistinct(int[] A, int K) {
        int count1 = calc(A, K);
        int count2 = calc(A, K - 1);
        return count1 - count2;
    }

    public static int calc(int[] A, int K) {
        if (K == 0) {
            return 0;
        }
        // 记录窗口中各元素出现的次数
        int[] counts = new int[A.length + 1];
        // 窗口中不同整数数量
        int windowCount = 0;
        int ans = 0;

        int left = 0, right = 0, len = A.length;
        while (right < len) {
            int num = A[right];
            counts[num]++;
            if (counts[num] == 1) {
                windowCount ++;
            }
            while (windowCount > K) {
                // 缩小窗口，使 windowCount 等于 K
                int leftVal = A[left];
                counts[leftVal] --;
                if (counts[leftVal] == 0) {
                    windowCount --;
                }
                left ++;
            }
            // 窗口中子数组数量
            ans += right - left + 1;
            right ++;
        }
        return ans;
    }
}
